package LeetCodeHot100TopInterview;

public class Q005_LongestPalindrome {

    //求最长回文子串 暴力O(n^2) 中心扩展法需要填充#符号
    //填充#符号 加虚轴 ==> 为了奇数长度和偶数长度的回文都能检索出来
    //虚轴添加什么字符都行！
    //Manacher 算法
    //前置概念：
    //回文半径（包含中心）  直径  区域
    //回文半径数组 每个位置的答案 ==> 加速流程 ==> 两数之和问题/动态规划思想
    //回文最右边界+中心
    //遍历 ：
    // 1)i 在 r 外 暴力扩
    // 2)i 在 r 内  中心一定在 i 左边  此 R中心、左边界、右边界都可知
    //    1)此 i 对称点的回文区域
    //       1) 区域在 L..R 内 i 的答案就是 i 对称点的答案
    //       2) 区域在 L...R 外  R就是右边界
    //       3) 区域压线 L就是中心回文区域的 L 边界 外扩尝试



    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0){
            return null;
        }
        //填充#
        char[] str = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        for (int i = 0; i < str.length; i++) {
            sb.append(str[i]);
            sb.append("#");
        }
        str = sb.toString().toCharArray();
        //回文半径数组
        int[] pArr = new int[str.length];
        //回文右边界
        int R = -1;
        //回文中心
        int C = -1;
        //以上两个同步更新的
        int max = Integer.MIN_VALUE;
        //最大回文中心
        int start = 0;
        int end = 0;
        for (int i = 0; i < str.length; i++) {
            //分类讨论
            //i的对称点 i从长度算理解成从头开始
            //对称点 c - (i - c) ==> 2c - i
            int symmetry = 2 * C - i;
            //最小回文半径 R > i ==> i在 r 内 否则 i 在 r 外 需要暴力扩 此时最小回文半径定为 1 即本身
            pArr[i] = R > i ? Math.min(R - i, pArr[symmetry]) : 1;

            //暴力扩
            while (i - pArr[i] >= 0 && i + pArr[i] < str.length){
                if (str[i - pArr[i]] == str[i + pArr[i]]){
                    pArr[i]++;
                }else {
                    //1) 区域在 L..R 内 i 的答案就是 i 对称点的答案
                    //2）区域在 L...R 外  R就是右边界
                    //以上两种情况在这会直接 break 省代码 规整条件
                    break;
                }
            }
            //更新
            if (i + pArr[i] > R){
                R = i + pArr[i];
                C = i;
            }
            //维持最大回文半径
            if (max < pArr[i]){
                max = pArr[i];
                start = i - max + 1 ;
                end = i + max - 1;
            }



        }
        sb = new StringBuilder();
        for (int i = start; i <= end; i++) {
            if (str[i] != '#')
            sb.append(str[i]);
        }
        //最长回文串 == 填充了#的回文半径 - 1
//        return max - 1;
        return sb.toString();
    }

    public static void main(String[] args) {
        Q005_LongestPalindrome fun = new Q005_LongestPalindrome();
        System.out.println(fun.longestPalindrome("babad"));
    }
}
